#include <vector>
#include <unordered_set>
#include <iostream>

using namespace std;

class Solution 
{
public:
    int firstMissingPositive(vector<int>& nums) 
    {
        if(nums.empty())
        {
            return 1;
        }
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] <= 0 || nums[i] > nums.size())
            {
                nums[i] = nums.size() + 1;
            }
        }
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] == nums.size() + 1)
            {
                continue;
            }
            int val = abs(nums[i]);
            if(val > 0 && val <= nums.size()) // nums[i] == -(n + 1)的情况，val = n + 1。越界
            {
                nums[val - 1] = 0 - abs(nums[val - 1]);
            }
        }
        int result = nums.size() + 1;
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] > 0)
            {
                result = i + 1;
                break;
            }
        }
        return result;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) 
{
    cout << "[";
    for(int i = 0; i < nums.size(); i++) 
    {
        cout << nums[i];
        if(i < nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() 
{
    Solution solution;
    
    // 测试案例1: [1,2,0]
    cout << "测试案例1:" << endl;
    vector<int> nums1 = {1, 2, 0};
    cout << "输入: nums = ";
    printArray(nums1);
    cout << endl;
    int result1 = solution.firstMissingPositive(nums1);
    cout << "输出: " << result1 << endl;
    cout << "期望: 3" << endl << endl;
    
    // 测试案例2: [3,4,-1,1]
    cout << "测试案例2:" << endl;
    vector<int> nums2 = {3, 4, -1, 1};
    cout << "输入: nums = ";
    printArray(nums2);
    cout << endl;
    int result2 = solution.firstMissingPositive(nums2);
    cout << "输出: " << result2 << endl;
    cout << "期望: 2" << endl << endl;
    
    // 测试案例3: [7,8,9,11,12]
    cout << "测试案例3:" << endl;
    vector<int> nums3 = {7, 8, 9, 11, 12};
    cout << "输入: nums = ";
    printArray(nums3);
    cout << endl;
    int result3 = solution.firstMissingPositive(nums3);
    cout << "输出: " << result3 << endl;
    cout << "期望: 1" << endl << endl;
    
    // 测试案例4: 空数组
    cout << "测试案例4 (空数组):" << endl;
    vector<int> nums4 = {};
    cout << "输入: nums = ";
    printArray(nums4);
    cout << endl;
    int result4 = solution.firstMissingPositive(nums4);
    cout << "输出: " << result4 << endl;
    cout << "期望: 1" << endl << endl;
    
    // 测试案例5: 单个元素1
    cout << "测试案例5 (单个元素1):" << endl;
    vector<int> nums5 = {1};
    cout << "输入: nums = ";
    printArray(nums5);
    cout << endl;
    int result5 = solution.firstMissingPositive(nums5);
    cout << "输出: " << result5 << endl;
    cout << "期望: 2" << endl << endl;
    
    // 测试案例6: 单个元素非1
    cout << "测试案例6 (单个元素非1):" << endl;
    vector<int> nums6 = {2};
    cout << "输入: nums = ";
    printArray(nums6);
    cout << endl;
    int result6 = solution.firstMissingPositive(nums6);
    cout << "输出: " << result6 << endl;
    cout << "期望: 1" << endl << endl;
    
    // 测试案例7: 连续正数
    cout << "测试案例7 (连续正数):" << endl;
    vector<int> nums7 = {1, 2, 3, 4, 5};
    cout << "输入: nums = ";
    printArray(nums7);
    cout << endl;
    int result7 = solution.firstMissingPositive(nums7);
    cout << "输出: " << result7 << endl;
    cout << "期望: 6" << endl << endl;
    
    // 测试案例8: 全负数
    cout << "测试案例8 (全负数):" << endl;
    vector<int> nums8 = {-1, -2, -3};
    cout << "输入: nums = ";
    printArray(nums8);
    cout << endl;
    int result8 = solution.firstMissingPositive(nums8);
    cout << "输出: " << result8 << endl;
    cout << "期望: 1" << endl << endl;
    
    // 测试案例9: 重复元素
    cout << "测试案例9 (重复元素):" << endl;
    vector<int> nums9 = {1, 1, 2, 2, 3};
    cout << "输入: nums = ";
    printArray(nums9);
    cout << endl;
    int result9 = solution.firstMissingPositive(nums9);
    cout << "输出: " << result9 << endl;
    cout << "期望: 4" << endl << endl;
    
    // 测试案例10: 大数值
    cout << "测试案例10 (大数值):" << endl;
    vector<int> nums10 = {1000, 1001, 1002};
    cout << "输入: nums = ";
    printArray(nums10);
    cout << endl;
    int result10 = solution.firstMissingPositive(nums10);
    cout << "输出: " << result10 << endl;
    cout << "期望: 1" << endl << endl;
    
    // 测试案例11: 乱序
    cout << "测试案例11 (乱序):" << endl;
    vector<int> nums11 = {3, 1, 6, 4, 5, 2};
    cout << "输入: nums = ";
    printArray(nums11);
    cout << endl;
    int result11 = solution.firstMissingPositive(nums11);
    cout << "输出: " << result11 << endl;
    cout << "期望: 7" << endl << endl;
    
    return 0;
}